package leetcode_200;

/**
 *@author 周杨
 *DungeonGame_174 恶魔游戏 每次走进一个格子 只能选择向下或者向右 格子里有加减的权值 要保证走到最后一个格子 且进入每个格子生命值>0 求最小起始生命值
 *describe:用动态规划 自底向上求最优解  AC 7%
 *2018年6月10日 下午3:18:39
 */
public class DungeonGame_174 {

	public static void main(String[] args) {
		int[][] dungeon=new int[][] {{-2,-3,3},{-5,-10,1},{10,30,-5}};
		int[][] dungeon1=new int[][] {{1,-3,3},{0,-2,0},{-3,-3,-3}};
		DungeonGame_174 test=new DungeonGame_174();
		System.out.println(test.calculateMinimumHP1(dungeon));

	}
	
	/**
	 * describe:思想错误 当前取最小支出未必能拿到最大剩余
	 * 2018年6月10日 下午12:21:02
	 */
	public int calculateMinimumHP(int[][] dungeon) {
		int row=dungeon.length;
		int col=dungeon[0].length;
        int left[][]=new int[row][col];
        int min[][]=new int[row][col];
        min[0][0]=dungeon[0][0]>=0?1:1-dungeon[0][0];
        left[0][0]=dungeon[0][0]>=0?1+dungeon[0][0]:1;
        for(int i=1;i<row;++i) {//向下遍历第一列
        	int mayLeft=left[i-1][0]+dungeon[i][0];
        	min[i][0]=mayLeft>0?min[i-1][0]:min[i-1][0]-mayLeft+1;
        	left[i][0]=mayLeft>0?mayLeft:1;
        }
        for(int i=1;i<col;++i) {
            int mayLeft=left[0][i-1]+dungeon[0][i];
            min[0][i]=mayLeft>0?min[0][i-1]:min[0][i-1]-mayLeft+1;
            left[0][i]=mayLeft>0?mayLeft:1;
        }
        for(int i=1;i<row;++i)
        	for(int j=1;j<col;++j) {
        		int mayLeft1=left[i-1][j]+dungeon[i][j];
        		int down=mayLeft1>0?min[i-1][j]:min[i-1][j]-mayLeft1+1;
        		int mayLeft2=left[i][j-1]+dungeon[i][j];
        		int lef=mayLeft2>0?min[i][j-1]:min[i][j-1]-mayLeft2+1;
        		if(down>lef) {//应该往右走
        			min[i][j]=lef;
        			left[i][j]=mayLeft2>0?mayLeft2:1;
        		}
        		else {
        			left[i][j]=mayLeft1>0?mayLeft1:1;
        			min[i][j]=down;
        		}
        	}
        return min[row-1][col-1];
       }
	
	public int calculateMinimumHP1(int[][] dungeon) {
		int row=dungeon.length;
		int col=dungeon[0].length;
		int dp[][]=new int[row][col];
		dp[row-1][col-1]=dungeon[row-1][col-1]<=0?1-dungeon[row-1][col-1]:1;
		int mayLeft;
		for(int i=row-2;i>=0;--i) {
			mayLeft=dp[i+1][col-1]-dungeon[i][col-1];
			dp[i][col-1]=mayLeft<=0?1:mayLeft;
		}
		for(int i=col-2;i>=0;--i) {
			mayLeft=dp[row-1][i+1]-dungeon[row-1][i];
			dp[row-1][i]=mayLeft<=0?1:mayLeft;
		}
		for(int i=row-2;i>=0;--i)
			for(int j=col-2;j>=0;--j) {
				int downLeft=dp[i+1][j]-dungeon[i][j];
				int rightLeft=dp[i][j+1]-dungeon[i][j];
				if(downLeft<rightLeft) {
					dp[i][j]=downLeft<=0?1:downLeft;
				}
				else {
					dp[i][j]=rightLeft<=0?1:rightLeft;
				}
			}
		return dp[0][0];
		
	}
}
